package leetcode_800;

/**
 *@author 周杨
 *NumberOfSubarraysWithBoundedMaximum_795 给定一个区间 问一个给定数组里 有多少子数组里最大值不超过这个区间
 *describe:用滑动窗口记录合法区间 AC 100%
 *2018年10月23日 上午10:53:05
 */
public class NumberOfSubarraysWithBoundedMaximum_795 {
	
	public int numSubarrayBoundedMax(int[] A, int L, int R) {
		int left = 0, count = 0, res = 0;
		for (int right = 0; right < A.length; ++right) {
			if (A[right] >= L && A[right] <= R) {
				res += (right - left + 1);
				count = (right - left + 1);
			} else if (A[right] < L) {
				res += count;
			} else {
				left = right + 1;
				count = 0;
			}
		}
		return res;
	}

	
	/**
	 * describe:不知道哪里错了 也是一样的思想
	 * 2018年10月23日 上午10:51:47
	 */
	public int numSubarrayBoundedMax1(int[] A, int L, int R) {
        int left=-1,right=-1,res=0,max=-1;//定义滑动窗口的边界  left表示合法的左边界 right表示不合法的左边界
        for(int i=0;i<A.length;++i) {
        	if(A[i]>max) {//有可能超过窗口限制
        		if(max<=R&&max>=L) {//窗口仍然有效
        			res+=i-left;
        			right=i;
        			max=A[i];
        		}
        		else {//窗口就地解散
        			left=i;
        			max=-1;
        			right=-1;
        		}
        	}
        	else if(A[i]<L) {//已经不合法了 但是自身仍能加入数组
        		if(right!=-1)//窗口仍然存在
        			res+=right-left;
        	}
        	else {//否则就是合理的
        		res+=i-left;
        		right=i;
        	}
        }
        return res;
    }
}
